import java.util.PriorityQueue;
import java.util.Queue;

public class Test {

    // 时间复杂度 O(N*logN + K*logN)
    public int[] smallestK1(int[] arr, int k) {
        int[] ret = new int[k];
        if (arr == null || k == 0){
            return ret;
        }
        Queue<Integer> minHeap = new PriorityQueue<>(arr.length);
        // O(N*logN)
        for (int x: arr) {
            minHeap.offer(x);
        }
        // O(K*logN)
        for (int i = 0; i < k; i++) {
            ret[i] = minHeap.poll();
        }
        return ret;
    }

    /**
     * 前 K 个最大元素
     * @param arr
     * @param k
     * @return
     */
    public int[] maxK(int[] arr,int k){
        int[] ret = new int[k];
        if (arr == null || k == 0){
            return ret;
        }
        Queue<Integer> minHeap = new PriorityQueue<>(k);

        // 1.遍历数组的前K个 放到堆当中        K * logK
        for (int i = 0; i < k; i++) {
            minHeap.offer(arr[i]);
        }
        // 2.遍历剩下 n-k 的元素，每次和堆顶元素进行比较   (n-k) * logK
        for (int i = k; i < arr.length; i++) {
            int val = minHeap.peek();
            // 堆顶元素小的时候，就出堆
            if (arr[i] > val){
                minHeap.poll();
                minHeap.offer(arr[i]);
            }
        }
        for (int i = 0; i < k; i++) {
            ret[i] = minHeap.poll();
        }
        return ret;
    }
    public static void main1(String[] args) {
        TestHeap testHeap = new TestHeap();
        int[] array = {27,15,19,18,28,34,65,49,25,37};
        testHeap.initElem(array);
        testHeap.creatHeap();
        testHeap.offer(80);
        System.out.println("aaaaaaaaaaaaa");
    }
}
